TOC-Universal Turing Machine

Describe a TM

A TM can be defined as a 7-tuple.

• by pseudo-code
• in a natural language

The input of a TM is a string. But the input of an algorithm can be any well-defined mathematical object. If TM and algorithm are equivalent, we need to describe the input of an algorithm as a string.

The description is an encoding of the input.

Suppose the input is $O$, then the encoding is denoted as $<O>$, which is a string over a specific alphabet.

We also assume that each $TM$ is programmed to decode $<O>$ and fully understand the meaning carried by $O$.

$A_{DFA}$

M can be designed on high-level. M = "On the input $<B,w>$, where $B$ is a DFA and $w$ is a string:

• 1. Simulate $B$ on w.
• 2. If $B$ accepts $w$, $M$ accepts $<B,w>$; otherwise $M$ rejects $<B,w>$."

The simulation uses a multi-head 2-D tape TM $M$.

Suppose $B=(Q_B,{\mathrm{\Sigma }}_B,{\delta }_B,q_{0B},F_B)$ has n states and m symbols in $\mathrm{\Sigma }$. The encoding of $B$, $w$ is as follows.

• $M$ puts $w$ on the "first" row if its tape.
• The "second" (below the first) row contains a sequence of symbols which represents the final states.
• From the third row, M has a 2 dimensional area of size $(n+2)\times (m+2)$ to represent ${\delta }_B$ as a transition table, s.t.
  • the first row and the first column contain only # to show the borders of the transition table;
  • the second row enumerates all symbols in $\mathrm{\Sigma }$ ; and
  • the second column enumerates all states in $Q$ and the first state is the start state.

M has 5 computation heads which do the following operations.

• $H_q$ iterates on the first column in the transition table and points to the current state of $B$.
• $H_s$ iterates on the first row in the transition table and searches the next input symbol from the row.
• $H_t$ follows $H_q$ and $H_s$ and checks the entry in the transition table to show the next state.
• $H_f$ iterates on the row for final states to verify whether $B$ enters a final state when all inputs are consumed.
• $H_i$ reads the input for $B$ from left to right.

Initially:

• $H_q$ points to the initial state in the transition table.
• $H_t$ is at the same position as $H_q$.
• $H_s$ is at the cell left to the first symbol (on the second row and the second column of the transition table).
• $H_f$ is at the leftmost final state on its row.
• $H_i$ is pointing to the first symbol in the input.

With the encoding of $B$ and the configuration of computation heads, $M$ simulates $B$ on input $w$ as follows:

1. If the cell pointed by $H_i$ has a symbol $s$, which is not empty.
2. $H_s$ searches $s$ on its row (moving right).
3. $H_t$ moves right simultaneously and stops when $H_s$ stops.
   ($H_t$ moves right and stops on the same column as $H_s$.)
4. Move $H_q$ (up and down) to the state pointed by $H_t$.
5. Move $H_t$ to the position of $H_q$ (using the border).
6. Initialize the position of $H_s$ (using the border).
7. Move $H_i$ right by one cell.
8. Repeat all the above until $H_i$ points to empty.
9. Use $H_f$ to search the state pointed by $H_q$ in final states.
   Accept if found; reject otherwise.

Universal TM

A Universal Turing Machine $U$ on the input $<M,w>$ is a special Turing machine in which:

• $<M>$ is the encoding Turing machine $M$,
• $<w>$ is the encoding of an input of $M$, and
• $U$ simulates $M$ on the input $w$.

The definition of a universal Turing machine captures the true meaning of Church-Turing Thesis.

TM is a universal computation model, which is the foundation of computers.